Trong các Quá trình Quyết định thời gian rời rạc Markov, cá quyết định được thực hiện tại các khoảng thời gian rời rạc. Tuy nhiên, đối với các Quá trình Quyết định Markov thời gian liên tục, các quyết định có thể được thực hiện tại bất kỳ thời gian nào mà người ra quyết định chọn. Khi so sánh với Quá trình Quyết định Markov thời gian Liên tục có thể mô hình hóa tốt hơn quá trình ra quyết định cho một hệ thống mà có động năng liên tục, có nghĩa là, các động năng của hệ thống được định nghĩa bởi các phương trình vi phân từng phần (PDE).

Định nghĩa

Để thảo luận về Quá trình Quyết định Markov thời gian liên tục, chúng tôi xin giới thiệu hai bộ ký hiệu:

Nếu không gian trạng thái và không gian hành động là hữu hạn,

• S {\displaystyle {\mathcal {S}}} : Không gian trạng thái;
• A {\displaystyle {\mathcal {A}}} : Không gian hành động;
• q ( i | j , a ) {\displaystyle q(i|j,a)} : S × A → △ S {\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \triangle {\mathcal {S}}} , hàm tốc độ chuyển tiếp;
• R ( i , a ) {\displaystyle R(i,a)} : S × A → R {\displaystyle {\mathcal {S}}\times {\mathcal {A}}\rightarrow \mathbb {R} } ,hàm phần thưởng.

Nếu không gian trạng thái và không gian hành động là liên tục,

• X {\displaystyle {\mathcal {X}}} : Không gian trạng thái.;
• U {\displaystyle {\mathcal {U}}} : Không gian kiểm soát tốt;
• f ( x , u ) {\displaystyle f(x,u)} : X × U → △ X {\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \triangle {\mathcal {X}}} , hàm tốc độ chuyển tiếp;
• r ( x , u ) {\displaystyle r(x,u)} : X × U → R {\displaystyle {\mathcal {X}}\times {\mathcal {U}}\rightarrow \mathbb {R} } , hàm tốc độ phần thưởng kiểu như r ( x ( t ) , u ( t ) ) d t = d R ( x ( t ) , u ( t ) ) {\displaystyle r(x(t),u(t))dt=dR(x(t),u(t))} , trong đó   R ( x , u ) {\displaystyle R(x,u)}  là hàm phần thưởng mà ta đã thảo luận trong trường hợp ở trên.

Bài toán

Giống như các Quá trình Quyết định Markov thời gian Rời rạc, trong Quá trình Quyết định Markov thời gian Liên tục, ta muốn tìm lời giải hoặc điều khiển tối ưu có thể cho chúng ta phần thưởng tích hợp mong  muốn tối ưu:

max E u [ ∫ 0 ∞ γ t r ( x ( t ) , u ( t ) ) ) d t | x 0 ] {\displaystyle \max \quad \mathbb {E} _{u}[\int _{0}^{\infty }\gamma ^{t}r(x(t),u(t)))dt|x_{0}]}

Trong đó  0 ≤ γ < 1 {\displaystyle 0\leq \gamma <1}

Hình thành công thức quy hoạch tuyến tính

Nếu không gian trạng thái và không gian hành động là hữu hạn, chúng ta có thể sử dụng quy hoạch tuyến tính để tìm lời giải tối ưu, đây là một trong những hướng tiếp cận sớm nhất được áp dụng. Ở đây chúng ta chỉ xem xét mô hình ergodic, nghĩa là MDP thời gian liên tục trở thành một ergodic Xích Markov thời gian rời rạc dưới một lời giải tĩnh. Dưới giả thiết này, mặc dù người ra quyết định có thể ra một quyết định tại bất kỳ thời gian tại trạng thái hiện tại, anh ta không thể thu lợi nhiều bằng cách thực hiện nhiều hơn 1 hành động. Sẽ tốt hơn cho anh ta để thực hiện một hành động tại thời điểm khi hệ thống đang dịch chuyển từ trạng thái hiện tại sang một trạng thái khác. Dưới vài điều kiện, (xem chi tiết Kết quả 3.14 của Quá trình Quyết định Markov thời gian Liên tục), nếu hàm giá trị tối ưu   V ∗ {\displaystyle V^{*}}  của chúng ta là độc lập với trạng thái i, chúng ta sẽ có bất phương trình sau:

g ≥ R ( i , a ) + ∑ j ∈ S q ( j | i , a ) h ( j ) ∀ i ∈ S a n d a ∈ A ( i ) {\displaystyle g\geq R(i,a)+\sum _{j\in S}q(j|i,a)h(j)\quad \forall i\in S\,\,and\,\,a\in A(i)}

Nếu tồn tại một hàm  h {\displaystyle h} , thì  V ¯ ∗ {\displaystyle {\bar {V}}^{*}}  sẽ là  g nhỏ nhất thỏa mãn phương trình ở trên. Để tìm  V ¯ ∗ {\displaystyle {\bar {V}}^{*}} , chúng ta có thể sử dụng mô hình quy hoạch tuyến tính sau đây:

• Quy hoạch tuyến tính nguyên thủy(P-LP)

Minimize g s.t g − ∑ j ∈ S q ( j | i , a ) h ( j ) ≥ R ( i , a ) ∀ i ∈ S , a ∈ A ( i ) {\displaystyle {\begin{aligned}{\text{Minimize}}\quad &g\\{\text{s.t}}\quad &g-\sum _{j\in S}q(j|i,a)h(j)\geq R(i,a)\,\,\forall i\in S,\,a\in A(i)\end{aligned}}}

• Quy hoạch tuyến tính kép(D-LP)

Maximize ∑ i ∈ S ∑ a ∈ A ( i ) R ( i , a ) y ( i , a ) s.t. ∑ i ∈ S ∑ a ∈ A ( i ) q ( j | i , a ) y ( i , a ) = 0 ∀ j ∈ S , ∑ i ∈ S ∑ a ∈ A ( i ) y ( i , a ) = 1 , y ( i , a ) ≥ 0 ∀ a ∈ A ( i ) a n d ∀ i ∈ S {\displaystyle {\begin{aligned}{\text{Maximize}}&\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\\{\text{s.t.}}&\sum _{i\in S}\sum _{a\in A(i)}q(j|i,a)y(i,a)=0\quad \forall j\in S,\\&\sum _{i\in S}\sum _{a\in A(i)}y(i,a)=1,\\&y(i,a)\geq 0\qquad \forall a\in A(i)\,\,and\,\,\forall i\in S\end{aligned}}}

y ( i , a ) {\displaystyle y(i,a)}  là một lời giải khả thi cho D-LP nếu  y ( i , a ) {\displaystyle y(i,a)}  là xa lạ và thỏa mãn các giới hạn trong bài toán D-LP. Một lời giải khả thi  y ∗ ( i , a ) {\displaystyle y^{*}(i,a)}  cho D-LP được cho là một lời giải tối ưu nếu

∑ i ∈ S ∑ a ∈ A ( i ) R ( i , a ) y ∗ ( i , a ) ≥ ∑ i ∈ S ∑ a ∈ A ( i ) R ( i , a ) y ( i , a ) {\displaystyle {\begin{aligned}\sum _{i\in S}\sum _{a\in A(i)}R(i,a)y^{*}(i,a)\geq \sum _{i\in S}\sum _{a\in A(i)}R(i,a)y(i,a)\end{aligned}}}

đối với tất cả các lời giải khả thi y(i,a) đối với D-LP. Khi chúng ta tìm thấy lời giải tối ưu  y ∗ ( i , a ) {\displaystyle y^{*}(i,a)} , chúng ta có thể sử dụng lời giải tối ưu này để thiết lập các giải pháp tối ưu.

Phương trình Hamilton-Jacobi-Bellman

Trong MDP thời gian liên tục, nếu không gian trạng thái và không gian hành động là liên tục, tiêu chuẩn tối ưu có thể được tìm thấy bằng cách giải phương trình đạo hàm riêng Hamilton-Jacobi-Bellman (HJB). Để thảo luận về phương trình HJB, chúng ta cần để viết lại bài toán của chúng ta như sau

V ( x ( 0 ) , 0 ) = max u ∫ 0 T r ( x ( t ) , u ( t ) ) d t + D [ x ( T ) ] s . t . d x ( t ) d t = f [ t , x ( t ) , u ( t ) ] {\displaystyle {\begin{aligned}V(x(0),0)=&{\text{max}}_{u}\int _{0}^{T}r(x(t),u(t))dt+D[x(T)]\\s.t.\quad &{\frac {dx(t)}{dt}}=f[t,x(t),u(t)]\end{aligned}}}

D( ⋅ {\displaystyle \cdot } ) là hàm phần thưởng cuối, x ( t ) {\displaystyle x(t)} là vector trạng thái hệ thống, u ( t ) {\displaystyle u(t)} là vector điều khiển hệ thống, ta sẽ phải đi tìm. f( ⋅ {\displaystyle \cdot } ) chỉ cách thức vector trạng thái thay đổi theo thời gian. Phương trình Hamilton-Jacobi-Bellman có dạng như sau:

0 = max u ( r ( t , x , u ) + ∂ V ( t , x ) ∂ x f ( t , x , u ) ) {\displaystyle 0={\text{max}}_{u}(r(t,x,u)+{\frac {\partial V(t,x)}{\partial x}}f(t,x,u))}

Chúng ta có thể giải phương trình trên để tìm điều khiển tối ưu  u ( t ) {\displaystyle u(t)} , sẽ cho chúng ta giá trị tối ưu  V ∗ {\displaystyle V^{*}}

Ứng dụng

Quá trình quyết định Markov thời gian liên tục được ứng dụng trong các hệ thống xếp hàng, các quá trình dịch bệnh và các quá trình dân số.